package 题目集.动态规划.背包问题;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 购买足量干草的最小花费 有n个提供干草的公司，每个公司都有两个信息： cost[i]代表购买1次产品需要花的钱
 * val[i]代表购买1次产品所获得的干草数量。 每个公司的产品都可以购买任意次 你一定要至少购买h数量的干草，返回最少要花多少钱。 测试链接 :
 * https://www.luogu.com.cn/problem/P2918 dp[i][j]:有i个公司可选，至少购买j数量干草的最小花费。
 */
public class ch08_完全背包 {
	static int n, sum;
	static int[] cost, val;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		sum = sc.nextInt();
		cost = new int[n + 1];
		val = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			val[i] = sc.nextInt();
			cost[i] = sc.nextInt();
		}
		dp = new int[n + 1][sum + 1];
		for (int[] d : dp) {
			Arrays.fill(d, -1);
		}
//		int res = dfs(n, sum);
//		int res = dp();
		int res = dp2();
		System.out.println(res);
	}

	static int[][] dp;

	public static int dfs(int i, int sum) {
		if (sum <= 0) {
			return 0;
		}
		if (dp[i][sum] != -1)
			return dp[i][sum];
		if (i == 0) {
			return Integer.MAX_VALUE;
		}
		int nochose = dfs(i - 1, sum);
		int chose = dfs(i, sum - val[i]);
		if (chose != Integer.MAX_VALUE) { // 存在枚举行为，进行优化
			chose += cost[i];
		}
		dp[i][sum] = Math.min(nochose, chose);
		return dp[i][sum];
	}

	public static int dp() {
		int[][] dp = new int[n + 1][sum + 1];
		Arrays.fill(dp[0], Integer.MAX_VALUE);
		dp[0][0] = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= sum; j++) {
				dp[i][j] = dp[i - 1][j]; // 不要当前
				if (j >= val[i]) { // 这里是一个转换点，并不是<val[i]就不选了
					int chose = dp[i][j - val[i]];
					if (chose != Integer.MAX_VALUE)
						chose += cost[i];
					dp[i][j] = Math.min(chose, dp[i][j]);
				} else {
					dp[i][j] = Math.min(dp[i][j], cost[i]);
				}
			}
		}
		return dp[n][sum];
	}

	/**
	 * 滚动数组优化，这里应该用压缩成dp[n+1][2]的，但那样不容易理解
	 * 
	 * @return
	 */
	public static int dp2() {
		int[][] dp = new int[2][sum + 1];
		int pre=0,cur = 0;
		Arrays.fill(dp[0], Integer.MAX_VALUE);
		dp[0][0] = 0;
		for (int i = 1; i <= n; i++) {
			pre=cur;
			cur=(cur+1)%dp.length;
			for (int j = 1; j <= sum; j++) {
				dp[cur][j] = dp[pre][j]; // 不要当前
				if (j >= val[i]) { // 这里是一个转换点，并不是<val[i]就不选了
					int chose = dp[cur][j - val[i]];
					if (chose != Integer.MAX_VALUE)
						chose += cost[i];
					dp[cur][j] = Math.min(chose, dp[cur][j]);
				} else {
					dp[cur][j] = Math.min(dp[cur][j], cost[i]);
				}
			}
		}
		return dp[cur][sum];
	}
}
